Rustでプロジェクトオイラーを始めてみた

こんにちは。サービスグループの武田です。

新しくプログラミング言語を身につけようと思ったとき、まずは基本的な文法をさらい、そして何かを作ってみるのが一番でしょう。人によってそれは、パーサコンビネータであったり、シンプルなWebサーバーであったりするかもしれません。

社内では、約1年前ほど前からTRPLベースでRustの学習を進める勉強会を実施していました。先日ひととおり終え、さてその後はどうしようということになったのですが、そこでやってみようとなったのがプロジェクトオイラーでした。

プロジェクトオイラー is 何

プロジェクトオイラーのAboutページから引用します。

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

About - Project Euler

簡単に言えば、数学やプログラミングに興味を持っている人向けの問題集というところでしょうか。与えられた問題を解いてサイトに入力すれば正誤の判定がもらえます（ユーザー登録が必要です）。そのため用いるプログラミング言語に制限はなく、また解ければ時間／空間的な効率はいったん無視して問題ありません。競技プログラミングと似ているような似ていないような、という雰囲気です。

ちなみに執筆時点（2020年9月29日）で717問が登録されています。また問題文が英語ですが、和訳したものを掲載してくれているWikiもあります。英語が苦手な方はこちらも参考にしてください。

Problem 1, Multiples of 3 and 5

雰囲気を知ってもらうために1問目をやってみましょう。

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

10までの自然数のうち3と5の倍数は3, 5, 6, 9で、合計は23です。では、1000までの3と5の倍数の総和はいくつでしょう。

という問題です。リスト操作に慣れた人であればぱっと次のようなコードが思い浮かぶでしょうか。

fn main() {
    println!(
        "{}",
        (1..1000)
            .filter(|n| n % 3 == 0 || n % 5 == 0)
            .sum::<usize>()
    );
}

問題文をそのままコーディングしたような素敵さがありますね。もちろんこのコードで何ら問題はありませんが、実は別の解法もあります。上記のコードは「プログラミング的」とでも言えるような解き方ですが、「数学的」な解き方もできます。

fn main() {
    println!(
        "{}",
        ((3 * 333 * (1 + 333)) + (5 * 199 * (1 + 199)) - (15 * 66 * (1 + 66))) / 2
    );
}

急にごちゃっとしたコードになりましたが、実は実行効率では優れています（まぁ高々1000なのでほぼ誤差でしょうけど）。何の計算をしているのかというと、「3の倍数の総和」+「5の倍数の総和」-「15の倍数の総和」をしています。単純に「3の倍数の総和」+「5の倍数の総和」だけだと、「15の倍数」を重複して足し込んでいるので引く必要があります。続いて「cの倍数の総和」の求め方ですが、「cの倍数」を順に並べると「初項 c、公差 c、項数 nの数列」を成すので、その数列の総和を求めればよいことになります。それをS_c(n)として公式を導くと次のようになります。

たとえばc=3, n=5とすると答えは45になりますが、これは3, 6, 9, 12, 15という3の倍数の数列の総和と一致します。あとはそれぞれの項数が分かれば公式に当てはめるだけです。項数はfloor(999 / c)で求められます。それぞれ333, 199, 66となることが分かるので、公式をそのままコーディングすると先ほどのプログラムになります（/ 2はくくっています）。

まとめ

問題が解けると気分がいいですね！必要な数学的知識は中学・高校程度のものがほとんどのはずですが結構忘れているものも多くあります。Rustの学習がベースにあるものの数学の学習もできて一石二鳥！ぜひみなさんもプロジェクトオイラー、取り組んでみてください。